package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/10 17:11
 * https://leetcode-cn.com/problems/course-schedule/
 */
public class Title207 {

    /**
     * 拓扑排序：(使用Map创建邻接表加快查找速度，BFS 借助入度表与邻接表 判断是否为有向无环图）
     * 先统计所有节点的入度，对于入度为0的节点就可以分离出来，然后把这个节点指向的节点的入度减一。
     * 一直做改操作，直到所有的节点都被分离出来。
     * 如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //value：前置课程
        Map<Integer, LinkedList<Integer>> hash = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            hash.put(i, new LinkedList<>());
        }
        //存储各个课程的入度
        int[] inDegree = new int[numCourses];
        //入度为0的顶点个数
        int count = 0;
        //创建邻接表
        for (int i = 0; i < prerequisites.length; i++) {
            hash.get(prerequisites[i][1]).add(prerequisites[i][0]);
            inDegree[prerequisites[i][0]]++;
        }
        //入度为0的队列
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                count++;
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            //每次从入度为0的节点出发
            Integer course = queue.poll();
            for (Integer nextCourse : hash.get(course)) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] == 0) {
                    count++;
                    queue.offer(nextCourse);
                }
            }
        }
        return count == numCourses;
    }



    /**
     * dfs：检测这个有向图中有没有环，只要存在环，课程就不能完成。
     * 创建邻接表，当访问一个结点的时候，应该递归访问它的前驱结点，直至前驱结点没有前驱结点为止。
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        //逆邻接表  value 前置节点
        Map<Integer, LinkedList<Integer>> graph = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new LinkedList<>());
        }
        //0 未被访问 1被当前节点访问 2被其他节点访问
        for (int i = 0; i < prerequisites.length; i++) {
            graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(graph, i, visited)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(Map<Integer,LinkedList<Integer>> graph, int startIndex, int[] visited) {
        if (visited[startIndex] == 1) {
            //被本轮的节点访问过，重复访问，即存在环
            return false;
        }
        if (visited[startIndex] == 2) {
            return true;
        }
        //未被访问过，标记访问“1”
        visited[startIndex] = 1;
        for (Integer nextCourse : graph.get(startIndex)) {
            if(!dfs(graph, nextCourse, visited)){
                return false;
            }
        }
        //本轮递归完，设置状态“2”
        visited[startIndex] = 2;
        return true;
    }


    public static boolean getAllTime(int numCourses, int[][] prerequisites) {
        Map<Integer, LinkedList<Integer>> graph = new HashMap<>();
        //入度
        int[] inDegree = new int[numCourses];
        for (int[] edge : prerequisites) {
            graph.computeIfAbsent(edge[1], k -> new LinkedList<>()).offer(edge[0]);
            inDegree[edge[0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                count++;
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                for (Integer e : graph.getOrDefault(queue.poll(), new LinkedList<>())) {
                    inDegree[e]--;
                    if (inDegree[e] == 0) {
                        count++;
                        queue.offer(e);
                    }
                }
            }
        }
        return count == numCourses;
    }

    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String[] tasks = sc.nextLine().trim().split(";");
        int numCourses = 2;
        int[][] prerequisites = {{1, 0}};
        getAllTime(numCourses, prerequisites);
    }


}
